巅峰赛15官方题解
T1
在题目给出的nnn个数字之中，针对于h1h_1h1 ，for循环枚举从左往右找到比他更大的第一个hih_ihi 即，否则输出−1-1−1。
T2
题目并未要求计算出最小值，因此可以选择使用二维数组保存每项菜肴的营养价值和其对应的营养种类，然后针对于每一种营养种类的价值累加判断即可。
T3.
当数组中所有的元素都是大于1的，那么一定合法，我们可以把前 n−1n - 1n−1 个数全变成1，多出来的部分加到最后一个 数上面。所以我们只需要考虑1的情况，我们可以令 cnt1cnt1cnt1 代表1的个数， cntcntcnt 代表非1的数和1的差值的和，我们只需要把 cntcntcnt 分配给 cnt1cnt1cnt1 个1即可。
例如
* 不合法的极端情况
这个样例不合法，因为3最多拿出2出来给前面的1，所以至少有一个1和之前一样。
* 合法的情况
这个样例是合法的，因为刚好可以从最后一个元素抽出3出来均匀分配给前面3个元素，使得数组中所有元素都不一样。
T4
首先我们需要对d∗id*_id∗i 进行预处理，求得他在一个星期当中的实际变化数值，通过取d∗id_*id∗ i mod A+BA+BA+B即可得出。
随后可以对其进行升序排列，去除重复项后得到序列E=E∗1,E∗2,...,EkE = {E*_1, E_*2,..., E_k}E=E∗1 ,E∗ 2,...,Ek 。
如果答案为Yes，那么序列EEE一定满足： 存在一个i(1≤i≤k)i(1 \leq i \leq k)i(1≤i≤k)，使得(E∗i+1−E∗i)(E*_{i+1} - E_*i)(E∗i+1 −E∗ i) mod (A+B)>B(A + B) > B(A+B)>B ， 边界值E∗k+1=E∗1E*_{k + 1} = E_*1E∗k+1 =E∗ 1。
我们可以尝试着枚举iii的取值，若满足即可输出Yes，否则输出No。
时间复杂度为:O(nlogn)O(nlogn)O(nlogn)
T5.
本题考虑分块做法。由于本题只有查询，所以我们可以想到离线做，我们只需要考虑两种情况：
* 1.当步长 ≥sqrt(n)\geq sqrt(n)≥sqrt(n)的时候，那么每次只要走 sqrt(n)sqrt(n)sqrt(n)步就能走完，我们可以暴力走，最坏时间复杂度O(nn)O(n\sqrt{n})O(nn )。
* 2.当步长 ≤sqrt(n)\leq sqrt(n)≤sqrt(n)的时候，这样步长很小，暴力会超时，但是可以发现这样的步长的种类不是很多，我们可以按步长进行排序，虽然起点可能不一样，但是终点都是在最后一个长度为sqrt(n)sqrt(n)sqrt(n)的块里面，所以我们可以从后往前推即可。这样的时间复杂度最坏也是 O(nn)O(n\sqrt{n})O(nn )。
T6.
本题首先应该不难想到要用 dpdpdp 来维护答案，我们令 dp[i]dp[i]dp[i] 表示 以第 iii 个数为结尾能得到的最大价值。那么
我们可以不断的枚举iii 前面的下标 jjj，令S=aj+aj+1+……a[i]S= a_j + a_{j + 1} +…… a[i]S=aj +aj+1 +……a[i]，则有三种情况：
* S=0S = 0S=0 ， dp[i]=max(dp[i],dp[j])dp[i] = max(dp[i], dp[j])dp[i]=max(dp[i],dp[j])
* S>0S > 0S>0， dp[i]=max(dp[i],dp[j−1]+i−j+1)dp[i] = max(dp[i], dp[j - 1] + i - j + 1)dp[i]=max(dp[i],dp[j−1]+i−j+1)
* S<0S < 0S<0 ， dp[i]=max(dp[i],dp[j−1]−i+j−1)dp[i] = max(dp[i], dp[j - 1] - i + j - 1)dp[i]=max(dp[i],dp[j−1]−i+j−1)
答案就是我们的dp[n]dp[n]dp[n]
但是很明显，这样会超时，我们可以仔细观察那 333 个式子，把 iii 和 jjj 所在式子分离出来：
* S=0S = 0S=0 ， dp[i]=max(dp[i],dp[j])dp[i] = max(dp[i], dp[j])dp[i]=max(dp[i],dp[j])
* S>0S > 0S>0， dp[i]=max(dp[i],dp[j−1]−j+i+1)dp[i] = max(dp[i], dp[j - 1] - j + i + 1)dp[i]=max(dp[i],dp[j−1]−j+i+1)
* S<0S < 0S<0 ， dp[i]=max(dp[i],dp[j−1]+j−i−1)dp[i] = max(dp[i], dp[j - 1] + j - i - 1)dp[i]=max(dp[i],dp[j−1]+j−i−1)
所以首先我们只需要将所有的前缀和当作下标，维护出 dp[j],dp[j−1]−j，dp[j−1]+jdp[j], dp[j - 1] - j， dp[j - 1] + jdp[j],dp[j−1]−j，dp[j−1]+j 的最大值即可，维护这个最大值可以用树状数组或者线段树等数据结构，然后每次求 dp[i]dp[i]dp[i]的时候，只需要在对应的区间上求对应的最大值即可，假设当前前缀和sis_isi 离散后的下标为 idxidxidx：
* 考虑S=0S = 0S=0 的情况，只需要在 [idx,idx][idx, idx][idx,idx] 中间找最大的 dp[j]dp[j]dp[j], 1≤j≤i1 \leq j \leq i1≤j≤i
* 考虑 S>0S > 0S>0 的情况，只需要在 [idx+1,n][idx + 1, n][idx+1,n]中间找 dp[j]−jdp[j] - jdp[j]−j 的最大值
* 考虑 S<0S < 0S<0 的情况，只需要在 [1,idx−1][1, idx - 1][1,idx−1]中间找 dp[j]+jdp[j] + jdp[j]+j的最大值
其次前缀会比较大，所以需要离散化。
时间复杂度 O(nlogn)O(nlogn)O(nlogn)
